[Coding034] LeetCode 061

Rotate List

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 链表的计数：设置一个指针，边后移，边计数；循环进行直到指针指向空；

• 链表的操作，务必把待操作节点的前一个节点找到，否则会导致链表断裂；

• 关于本题的k，很有意思的一个知识点；

  • cnt 和 k的关系，务必清楚；

  • k能整除cnt：$k\mathrm{\%}cnt==0$$k\%cnt==0$，意味着k是0，或者k是cnt的整数倍；

题目：61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4,5], k = 2
2
Output: [4,5,1,2,3]

Example 2:

xxxxxxxxxx
2
1
Input: head = [0,1,2], k = 4
2
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].

• -100 <= Node.val <= 100

• 0 <= k <= 2 * 109

代码1（配 · 手绘过程图）

xxxxxxxxxx
45
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode rotateRight(ListNode head, int k) {
13
        ListNode cp = head;
14
        int cnt = 0;
15

16
        while (cp != null)
17
        {
18
            cnt++;
19
            cp = cp.next;
20
        }
21

22
        if (cnt == 0 || cnt == 1 || k == 0 || k % cnt == 0) return head;
23

24
        int t = k % cnt;  // 翻t个
25
        cp = head;
26
        
27
        int temp = cnt - t - 1;
28
        while (temp != 0)
29
        {
30
            temp--;
31
            cp = cp.next;
32
        }
33
        ListNode ret = cp.next;
34
        ListNode p = cp;
35
        while (p.next != null)
36
        {
37
            p = p.next;
38
        }
39

40
        cp.next = null;
41
        p.next = head;
42

43
        return ret;
44
    }
45
}

代码解读 | 评价

这个代码的可读性比较差。具体的思想绘制如图。按照思想即可编写代码。

需要注意点是：特殊情况的判定。

• 什么时候不翻转？

  • 翻转的k次刚好能够整除整个链表的长度，例如，长度为5的链表，翻转0次、5次、10次、15次还是它本身；

  • 链表如果本身的长度是1或者是空，那么也不会翻转。因为1和空任其翻转还是它自己；

• 翻转的本质是什么？

  • 【原始链表】：①→②→③→④→⑤→⑥→⑦→⑧

  • 【翻转一次】：⑧→①→②→③→④→⑤→⑥→⑦

  • 【翻转二次】：⑦→⑧→①→②→③→④→⑤→⑥

  • 【翻转三次】：⑥→⑦→⑧→①→②→③→④→⑤

  • 就是截断尾巴安装在头部。

复杂度分析